#include<iostream>
#include<vector>
using namespace std;

int searchInsert(vector<int>& nums,int target){
    int left=0,right=nums.size()-1;
    int mid;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(nums[mid]<=target){
            left = mid;
        }
        else{
            right = mid - 1;
        }
    }

    if(nums[left]<target){
        return left+1;
    }
    return left;
}

int peakIndexInMountainArray(vector<int>& arr){
    int left = 0, right = arr.size() - 1;
    int mid = 0;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(arr[mid-1]>arr[mid]){
            left = mid;
        }
        if(arr[mid]>arr[mid+1]){
            right = mid - 1;
        }
    }

    return left;
}

int findPeakElement(vector<int>& nums){
    int left = 0, right = nums.size() - 1;
    int mid=0;

    while(left<right){
        mid = left + (right - left + 1) / 2;

        if(nums[mid-1]<nums[mid]){
            left = mid;
        }
        if(nums[mid]>nums[mid+1]){
            right = mid - 1;
        }
    }

    return left;
}

int main(){
    int target=2;
    vector<int> nums = {1,3,5,6};
    vector<int> arr = {0, 2, 1, 0};
    vector<int> nums1 = {1, 2, 1, 3, 5, 6, 4};
    int ret = searchInsert(nums, target);

    cout << ret;
    return 0;
}